# 剑指Offer题解 - Day45

# 剑指 Offer 16. 数值的整数次方

实现 pow(x, n)，即计算 x 的 n 次幂函数（即，x^n）。不得使用库函数，同时不需要考虑大数问题。

示例1：

输入：x = 2.00000, n = 10
输出：1024.00000

1
2

提示：

100.0 < x < 100.0
231 <= n <= 2311
104 <= xn <= 104

思路：

首先考虑使用循环来不断进行相乘。如果n是负数，则最终求出倒数即可。不难写出如下代码：

# 循环

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function(x, n) {
    let res = 1;
    for (let i = 0; i < Math.abs(n); i++) {
        res *= x;
    }
    return n < 0 ? 1 / res : res;
};

1
2
3
4
5
6
7
8
9
10
11
12

时间复杂度 O(n)。
空间复杂度 O(1)。

分析：

这样处理确实简单粗暴，但是无法通过提交。因为当n很大的时候，会进行太多次的循环次数，最终就会超出时间限制。因此此方法不可取。

# 二分法

通过二分的方式可以将时间复杂度由O(N)降低至O(logN) 。二分法的思路是：

如果指数n为偶数，那么x^n就等同于(x^2)^(n/2)
如果指数n为奇数，那么x^n就等同于x(x^2)^(Math.floor(n/2)) ，外层的指数是向下取整
奇偶数可以通过n & 1是否等于1判断，等于1就是奇数，等于0就是偶数
指数除以2并向下取整可以通过 n >> 1

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function(x, n) {
    if (n === 0) return 1; // 特殊情况处理
    if (n === 1) return x;
    if (n === -1) return 1 / x;
    let result = myPow(x, n >> 1); // 计算指数除以2并向下取整的结果
    result *= result; // 结果进行平方
    if ((n & 1) === 1) result *= x; // 如果n是奇数则结果再乘以x
    return result;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14

时间复杂度 O(logn)。
空间复杂度 O(1)。

分析：

首先处理一些极值情况。尤其是第三条，当n === -1 时，直接返回倒数。这样就不用事先处理n到底是正数还是负数的情况。因为如果n是负数，那么不断执行n >> 1 就会执行到n === -1的情况。

然后对指数进行除以2并向下取整计算出结果，对结果进行平方处理。如果说n就是偶数，那么上述的两步操作和不对指数进行除以2直接计算得出的结果是一样的。如果说n是奇数，需要再对结果乘以x，两者才相等。

如此计算，就可以将时间复杂度降低至O(logn) 。同样是相乘，x相乘n次和x相乘(n / 2)次再将结果相乘，后者可以降低指数级的相乘次数，所以此方法可以大幅降低相乘的次数，最终也不会超时。

# 总结

本题采用二分法的思想进行题解。逐个相乘是最笨的办法，但是无法通过提交，因此不能使用。二分法可以大大的降低重复相乘的次数，并且可以确保不会超时。

复杂度方面，二分的时间复杂度为对数级别。result变量占用常数级别大小的额外空间。

剑指Offer题解 - Day44 剑指Offer题解 - Day46